#include<stdio.h>
#include<stdbool.h>
#include<assert.h>
#include<stdlib.h>
typedef char STDataType;
typedef struct Stack
{
    STDataType* arr;
    int top;
    int capacity;
}ST;
void StackInit(ST* st)
{
    st->arr = NULL;
    st->top = st->capacity = 0;
}
void StackPush(ST* st, STDataType x)
{
    assert(st);
    if (st->top == st->capacity)
    {
        int newcapacity = st->capacity == 0 ? 4 : 2 * (st->capacity);
        STDataType* pcur = (STDataType*)realloc(st->arr, newcapacity * sizeof(STDataType));
        if (pcur == NULL)
        {
            perror("realloc fail\n");
            exit(1);
        }
        st->capacity = newcapacity;
        st->arr = pcur;
    }
    st->arr[st->top] = x;
    st->top++;
}
bool StackEmpty(ST* st)
{
    assert(st);
    return st->top == 0;
}
STDataType StackTop(ST* st)
{
    assert(!StackEmpty(st));
    return st->arr[st->top - 1];
}
void StackPop(ST* st)
{
    assert(!StackEmpty(st));
    st->top--;
}
void StackDestroy(ST* st)
{
    free(st->arr);
    st->arr = NULL;
    st->top = st->capacity = 0;
}
bool isValid(char* s)
{
    ST st;
    StackInit(&st);
    char* pi = s;
    while ((*pi) != '\0')
    {
        if ((*pi == '(') || (*pi == '{') || (*pi == '['))
        {
            StackPush(&st, *pi);
        }
        else
        {
            if (StackEmpty(&st))
                return false;
            char ps = StackTop(&st);
            if ((ps == '[') && (*pi != ']') || (ps == '{') && (*pi != '}') || (ps == '(') && (*pi != ')'))
            {
                StackDestroy(&st);
                return false;
            }
            StackPop(&st);
        }
        pi++;
    }
    bool ret = StackEmpty(&st) ? true : false;
    StackDestroy(&st);
    return ret;
}
int main()
{
    char arr[2] = "{}";
    isValid(&arr);
}